﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sudoku
{
    public class Grille
    {
        private int[,] grille;

        public Grille()
        {
            grille = new int[,]{
                {9,0,0,1,0,0,0,0,5},
                {0,0,5,0,9,0,2,0,1},
                {8,0,0,0,4,0,0,0,0},
                {0,0,0,0,8,0,0,0,0},
                {0,0,0,7,0,0,0,0,0},
                {0,0,0,0,2,6,0,0,9},
                {2,0,0,3,0,0,0,0,6},
                {0,0,0,2,0,0,9,0,0},
                {0,0,1,9,0,4,5,7,0}};

            /*
             *grille complète:
             * {
                {6,3,2,7,8,1,9,4,5},
                {4,8,7,5,9,6,2,1,3},
                {5,1,9,2,4,3,8,7,6},
                {8,6,4,3,5,2,7,9,1},
                {7,5,1,9,6,8,3,2,4},
                {2,9,3,1,7,4,6,5,8},
                {9,4,5,6,3,7,1,8,2},
                {1,7,6,8,2,5,4,3,9},
                {3,2,8,4,1,9,5,6,7}
                };
             * test:
             * {
                {9,0,0,1,0,0,0,0,5},
                {0,0,5,0,9,0,2,0,1},
                {8,0,0,0,4,0,0,0,0},
                {0,0,0,0,8,0,0,0,0},
                {0,0,0,7,0,0,0,0,0},
                {0,0,0,0,2,6,0,0,9},
                {2,0,0,3,0,0,0,0,6},
                {0,0,0,2,0,0,9,0,0},
                {0,0,1,9,0,4,5,7,0}}
             * 
             *grille de 0: 
             *{
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0}}
             *
             */
        }

        public int get_valeur_grille(Grille g, int x, int y)
        {
            return g.grille[x, y];
        }

        public void set_valeur_grille(Grille g, int x, int y, int valeur)
        {
            g.grille[x, y] = valeur;
        }

        public void afficher_grille(Grille g)
        {
            int i, j;
            for (i = 0; i < 9; i++)
            {
                for (j = 0; j < 9; j++)
                {
                    System.Console.Write(g.grille[i, j]);
                    System.Console.Write("|");
                }
                System.Console.WriteLine();
            }
        }

        public bool presence_dans_ligne(int valeur, Grille g, int i)
        {
            int j;
            for (j = 0; j < 9; j++)
            {
                if (g.get_valeur_grille(g, i, j) == valeur)
                {
                    return true;
                }
            }
            return false;
        }

        public bool presence_dans_colonne(int valeur, Grille g, int j)
        {
            int i;
            for (i = 0; i < 9; i++)
            {
                if (g.get_valeur_grille(g, i, j) == valeur)
                {
                    return true;
                }
            }
            return false;
        }

        public bool presence_dans_carre(int valeur, Grille g, int x, int y)
        {
            int i, j;
            int i1 = (x / 3) * 3, j1 = (y / 3) * 3;

            for (i = i1; i <= i1 + 2; i++)
            {
                for (j = j1; j <= j1 + 2; j++)
                {
                    if (g.get_valeur_grille(g, i, j) == valeur)
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        public bool backtracking(Grille g, int position) // renvoie vrai si la grille se termine, faux sinon
        {
            int i = position / 9, j = position % 9;
            int k;
            System.Console.WriteLine(position);
            if (position == 81)
                return true;

            if (g.get_valeur_grille(g, i, j) != 0)
                return backtracking(g, position + 1);

            for (k = 1; k <= 9; k++)
            {

                if ((!presence_dans_ligne(k, g, i)) && (!presence_dans_colonne(k, g, j)) && (!presence_dans_carre(k, g, i, j)))
                {
                    set_valeur_grille(g, i, j, k);

                    if (backtracking(g, position + 1))
                        return true;
                }
            }

            set_valeur_grille(g, i, j, 0);
            return false;
        }
    }
}
